Search Results

Documents authored by Upfal, Eli

Document
DOI: 10.4230/LIPIcs.ITC.2021.9
On the Complexity of Anonymous Communication Through Public Networks

Authors: Megumi Ando, Anna Lysyanskaya, and Eli Upfal

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Abstract
Onion routing is the most widely used approach to anonymous communication online. The idea is that Alice wraps her message to Bob in layers of encryption to form an "onion" and routes it through a series of intermediaries. Each intermediary’s job is to decrypt ("peel") the onion it receives to obtain instructions for where to send it next. The intuition is that, by the time it gets to Bob, the onion will have mixed with so many other onions that its origin will be hard to trace even for an adversary that observes the entire network and controls a fraction of the participants, possibly including Bob. Despite its widespread use in practice, until now no onion routing protocol was known that simultaneously achieved, in the presence of an active adversary that observes all network traffic and controls a constant fraction of the participants, (a) anonymity; (b) fault-tolerance, where even if a few of the onions are dropped, the protocol still delivers the rest; and (c) reasonable communication and computational complexity as a function of the security parameter and the number of participants. In this paper, we give the first onion routing protocol that meets these goals: our protocol (a) achieves anonymity; (b) tolerates a polylogarithmic (in the security parameter) number of dropped onions and still delivers the rest; and (c) requires a polylogarithmic number of rounds and a polylogarithmic number of onions sent per participant per round. We also show that to achieve anonymity in a fault-tolerant fashion via onion routing, this number of onions and rounds is necessary. Of independent interest, our analysis introduces two new security properties of onion routing - mixing and equalizing - and we show that together they imply anonymity.
Cite as

Megumi Ando, Anna Lysyanskaya, and Eli Upfal. On the Complexity of Anonymous Communication Through Public Networks. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 9:1-9:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ando_et_al:LIPIcs.ITC.2021.9,
  author =	{Ando, Megumi and Lysyanskaya, Anna and Upfal, Eli},
  title =	{{On the Complexity of Anonymous Communication Through Public Networks}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{9:1--9:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.9},
  URN =		{urn:nbn:de:0030-drops-143282},
  doi =		{10.4230/LIPIcs.ITC.2021.9},
  annote =	{Keywords: Anonymity, privacy, onion routing}
}
Document
DOI: 10.4230/LIPIcs.WABI.2018.18
Differentially Mutated Subnetworks Discovery

Authors: Morteza Chalabi Hajkarim, Eli Upfal, and Fabio Vandin

Published in: LIPIcs, Volume 113, 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)

Abstract
We study the problem of identifying differentially mutated subnetworks of a large gene-gene interaction network, that is, subnetworks that display a significant difference in mutation frequency in two sets of cancer samples. We formally define the associated computational problem and show that the problem is NP-hard. We propose a novel and efficient algorithm, called DAMOKLE to identify differentially mutated subnetworks given genome-wide mutation data for two sets of cancer samples. We prove that DAMOKLE identifies subnetworks with a statistically significant difference in mutation frequency when the data comes from a reasonable generative model, provided enough samples are available. We test DAMOKLE on simulated and real data, showing that DAMOKLE does indeed find subnetworks with significant differences in mutation frequency and that it provides novel insights not obtained by standard methods.
Cite as

Morteza Chalabi Hajkarim, Eli Upfal, and Fabio Vandin. Differentially Mutated Subnetworks Discovery. In 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 113, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hajkarim_et_al:LIPIcs.WABI.2018.18,
  author =	{Hajkarim, Morteza Chalabi and Upfal, Eli and Vandin, Fabio},
  title =	{{Differentially Mutated Subnetworks Discovery}},
  booktitle =	{18th International Workshop on Algorithms in Bioinformatics (WABI 2018)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-082-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{113},
  editor =	{Parida, Laxmi and Ukkonen, Esko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2018.18},
  URN =		{urn:nbn:de:0030-drops-93202},
  doi =		{10.4230/LIPIcs.WABI.2018.18},
  annote =	{Keywords: Cancer genomics, network analysis, combinatorial algorithm}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.144
Practical and Provably Secure Onion Routing

Authors: Megumi Ando, Anna Lysyanskaya, and Eli Upfal

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In an onion routing protocol, messages travel through several intermediaries before arriving at their destinations; they are wrapped in layers of encryption (hence they are called "onions"). The goal is to make it hard to establish who sent the message. It is a practical and widespread tool for creating anonymous channels. For the standard adversary models - passive and active - we present practical and provably secure onion routing protocols. Akin to Tor, in our protocols each party independently chooses the routing paths for his onions. For security parameter lambda, our differentially private solution for the active adversary takes O(log^2 lambda) rounds and requires every participant to transmit O(log^{4} lambda) onions in every round.
Cite as

Megumi Ando, Anna Lysyanskaya, and Eli Upfal. Practical and Provably Secure Onion Routing. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 144:1-144:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ando_et_al:LIPIcs.ICALP.2018.144,
  author =	{Ando, Megumi and Lysyanskaya, Anna and Upfal, Eli},
  title =	{{Practical and Provably Secure Onion Routing}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{144:1--144:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.144},
  URN =		{urn:nbn:de:0030-drops-91482},
  doi =		{10.4230/LIPIcs.ICALP.2018.144},
  annote =	{Keywords: Anonymity, traffic analysis, statistical privacy, differential privacy}
}
Document
DOI: 10.4230/DagRep.7.4.1
Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141)

Authors: Bodo Manthey, Claire Mathieu, Heiko Röglin, and Eli Upfal

Published in: Dagstuhl Reports, Volume 7, Issue 4 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17141 "Probabilistic Methods in the Design and Analysis of Algorithms". Probabilistic methods play a central role in theoretical computer science. They are a powerful and widely applied tool used, for example, for designing efficient randomized algorithms and for establishing various lower bounds in complexity theory. They also form the basis of frameworks like average-case and smoothed analysis, in which algorithms are analyzed beyond the classical worst-case perspective. The seminar was on probabilistic methods with a focus on the design and analysis of algorithms. The seminar helped to consolidate the research and to foster collaborations among the researchers who use probabilistic methods in different areas of the design and analysis of algorithms.
Cite as

Bodo Manthey, Claire Mathieu, Heiko Röglin, and Eli Upfal. Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141). In Dagstuhl Reports, Volume 7, Issue 4, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{manthey_et_al:DagRep.7.4.1,
  author =	{Manthey, Bodo and Mathieu, Claire and R\"{o}glin, Heiko and Upfal, Eli},
  title =	{{Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141)}},
  pages =	{1--22},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{4},
  editor =	{Manthey, Bodo and Mathieu, Claire and R\"{o}glin, Heiko and Upfal, Eli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.4.1},
  URN =		{urn:nbn:de:0030-drops-75452},
  doi =		{10.4230/DagRep.7.4.1},
  annote =	{Keywords: analysis of algorithms, average-case analysis, random graphs, randomized algorithms, smoothed analysis, sub-linear algorithms}
}
Document
DOI: 10.4230/DagSemProc.07391.1
07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms

Authors: Martin Dietzfelbinger, Shang-Hua Teng, Eli Upfal, and Berthold Vöcking

Published in: Dagstuhl Seminar Proceedings, Volume 7391, Probabilistic Methods in the Design and Analysis of Algorithms (2007)

Abstract
From 23.09.2007 to 28.09.2007, the Dagstuhl Seminar 07391 "Probabilistic Methods in the Design and Analysis of Algorithms''was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. The seminar brought together leading researchers in probabilistic methods to strengthen and foster collaborations among various areas of Theoretical Computer Science. The interaction between researchers using randomization in algorithm design and researchers studying known algorithms and heuristics in probabilistic models enhanced the research of both groups in developing new complexity frameworks and in obtaining new algorithmic results. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Martin Dietzfelbinger, Shang-Hua Teng, Eli Upfal, and Berthold Vöcking. 07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms. In Probabilistic Methods in the Design and Analysis of Algorithms. Dagstuhl Seminar Proceedings, Volume 7391, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{dietzfelbinger_et_al:DagSemProc.07391.1,
  author =	{Dietzfelbinger, Martin and Teng, Shang-Hua and Upfal, Eli and V\"{o}cking, Berthold},
  title =	{{07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms}},
  booktitle =	{Probabilistic Methods in the Design and Analysis of Algorithms},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7391},
  editor =	{Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V\"{o}cking},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07391.1},
  URN =		{urn:nbn:de:0030-drops-12915},
  doi =		{10.4230/DagSemProc.07391.1},
  annote =	{Keywords: Algorithms, Randomization, Probabilistic analysis, Complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact